// 接雨水
//// 双指针法
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), water = 0;
        if(n <= 2) return 0;

        int left = 0, right = n-1;
        int leftMax = 0, rightMax = 0;

        while(left < right)
        {
            if(height[left] < height[right])
            {
                if(height[left] > leftMax) leftMax = height[left];
                else water += leftMax - height[left];
                left++;
            }
            else
            {
                if(height[right] > rightMax) rightMax = height[right];
                else water += rightMax -  height[right];
                right--;
            }
        }

        return water;

    }
};
//// 动态规划
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n <= 2) return 0;
        vector<int> left(n);
        vector<int> right(n);
        
        left[0] = height[0];
        for(int i = 1; i < n; i++) left[i] = max(left[i-1], height[i]);
        right[n-1] = height[n-1];
        for(int i = n-2; i >= 0; i--) right[i] = max(right[i+1], height[i]);

        int water = 0;
        for(int i = 0; i < n; i++) water += min(left[i], right[i]) - height[i];
        return water;
    }
};

// 岛屿数量
class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int m = 0, n = 0;
    bool vst[310][310] = {false};
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        int ret = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == '1' && !vst[i][j])
                {
                    ret++;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        vst[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vst[x][y])
            {
                dfs(grid, x, y);
            }
        }
    }
};